#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
	char data;
	struct Node *next;
}Node;

//初始化
void InitList(Node* &L)
{
	L=(Node*)malloc(sizeof(Node));
	L->next=NULL;
}

//创建
void CreatList(Node*&L,char a[],int n)
{
    Node*p=L,*s;
    for(int i=0;i<n;i++)
    {
        s=(Node*)malloc(sizeof(Node));
        p->next=s;
        s->data=a[i];
        p=s;
    }
    p->next=NULL;
}

//销毁
void DestroyList(Node* L)
{
	Node*p,*pre;
	pre=L;
	p=L->next;
	while(p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}

//输出
void DispList(Node* L)
{
	Node*p=L->next;
	while(p!=NULL)
	{
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
}

//插入
bool ListInsert(Node* &L,int i,char e)
{
	if(i<=0)
		return false;
	int j=0;
	Node*p=L;
	Node*s;
	while(j<i-1&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	else
	{
		s=(Node*)malloc(sizeof(Node));
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
}

//删除
bool ListDelete(Node* &L,int i)
{
	if(i<=0)
		return false;
	int j=0;
	Node*p=L,*q;
	while(j<i-1&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	else
	{
		q=p->next;
		if(q==NULL)
			return false;
		p->next=q->next;
		free(q);
		return true;
	}
}

//划分
void split(Node*&L)
{
    int cnt=1;
    Node*p=L->next,*pp=p->next;
    while(pp!=NULL)
    {
        cnt++;
        if(p->data>pp->data)//该数据小于基准
        {
            ListInsert(L,1,pp->data);
            pp=pp->next;
            ListDelete(L,cnt+1);
        }
        else
            pp=pp->next;
        
    }
}

int main()
{
    Node* h;
    char a[]="daxgdchaeb";
    InitList(h);
    CreatList(h,a,11);
    split(h);
    DispList(h);
    DestroyList(h);
}